//
//  CCDynamicRoute.hpp
//  leetcode
//
//  Created by hellobike07499 on 2019/8/26.
//  Copyright © 2019 hellobike07499. All rights reserved.
//

#ifndef CCDynamicRoute_hpp
#define CCDynamicRoute_hpp

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

class CCDynamicRoute{
public:
    void test(){
//        cout << climbStairs(44) << endl;
        test3();
    }
    
    void test1(){
        vector<int> t = {7,1,5,3,6,4};
        cout << maxProfit(t) << endl;
        
        vector<int> t1 = {2,7,1,11,4};
        cout << maxProfit(t1) <<endl;
    }
    
    void test2(){
        vector<int> t = {-2,1,-3,4,-1,2,1,-5,4};
        cout << maxSubArray(t) << endl;
    }
    
    void test3(){
        vector<int> t = {1,2,3,1};
        cout << rob(t) << endl;
    }
private:
    int climbStairs(int n) {
        if(n <= 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        vector<int> contain(n, 0);
        contain[0] = 1;
        contain[1] = 2;
        
        for (int i = 2; i < n; i++) {
            contain[i] = contain[i - 1] + contain[i - 2];
        }
        
        return contain[n - 1];
    }
    
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1) return 0;
        
        int max = 0;
        int min = prices[0];
        for (int i = 0; i < prices.size(); i++) {
            if(prices[i] > min){
                continue;
            }
            min = prices[i];
            
            for (int j = i + 1; j < prices.size(); j++) {
                int n = prices[j] - prices[i];
                if(n > max){
                    max = n;
                }
            }
        }
        return max;
    }
    
    int maxSubArray(vector<int>& nums) {
        if(nums.size() <= 0) return 0;
        if(nums.size() == 1) return nums[0];
        
//        int c = (int) nums.size();
//        vector<int> sum(nums.size(), 0);
//        sum[c - 1] = nums[c - 1];
//        int max = sum[c - 1];
//
//        for (int j = (int)nums.size() - 2; j > 0; j--) {
//            sum[j] = sum[j + 1] + nums[j];
//            if(sum[j] > max){
//                max = sum[j];
//            }
//        }
        
        int max = nums[0];
        vector<int> sums(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++) {
            if(i == 0){
                sums[0] = nums[0];
            }else{
                sums[i] = sums[i - 1] > 0 ? (sums[i - 1] + nums[i]) : nums[i];
            }
            
            if(sums[i] > max){
                max = sums[i];
            }
        }
        return max;
    }
    
    int rob(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        
        vector<int> sums(nums.size(), 0);
        sums[0] = nums[0];
        sums[1] = nums[0] > nums[1] ? nums[0] : nums[1];
        
        for (int i = 2; i < nums.size(); i++) {
            int tmp = sums[i - 2] + nums[i];
            sums[i] = tmp > sums[i - 1] ? tmp : sums[i - 1];
        }
        return *(sums.rbegin());
    }
};

#endif /* CCDynamicRoute_hpp */
